package org.shj.suanfa

import scala.collection.mutable._

/**
 * 给定元素全为非负整数的非空数组nums，数组的度等于出现最多的元素的次数，找到具有和nums相同度的连续子串的最小长度
 * 如： 输入 [1,4,4,3,1], 输出 4
 * 注意点： 有可能有多个元素的次数都是最多的次数
 */
object S003 {
  def main(args: Array[String]): Unit = {
    val array = Array(1, 4, 3, 4, 1)
    
    //ArrayBuffer中第一个值为此元素的起始位置，第二个值为此元素的最后一个位置，第三个值是出现的次数
    val map = Map[Int, ArrayBuffer[Int]]() 
    
    for(i <- 0 to array.length - 1){
      val ab = map.getOrElse(array(i), ArrayBuffer(i,i, 0))
      ab(1) = i
      ab(2) += 1
      if(!map.contains(array(i))){
        map += (array(i) -> ab)
      }
    }
    
    //获得数组的度
    val max = map.max(new Ordering[(Int, ArrayBuffer[Int])](){
      def compare(a: (Int, ArrayBuffer[Int]), b: (Int, ArrayBuffer[Int])) : Int = {
        a._2(2) compare b._2(2)
      }
    })
    
    val degree = max._2(2)
    val min = map.filter(_._2(2) == degree).min(new Ordering[(Int, ArrayBuffer[Int])](){
      def compare(a: (Int, ArrayBuffer[Int]), b: (Int, ArrayBuffer[Int])) : Int = {
        (a._2(1) - a._2(0)) compare (b._2(1) - b._2(0))
      }
    })    
    
    println(min._2(1) - min._2(0) + 1)
  }
}